package com.tsx.leetcode.hot100.medium;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * <a href="https://leetcode.cn/problems/longest-substring-without-repeating-characters">无重复字符的最长子串</a>
 */
public class Q3LengthOfLongestSubstring {
    public static void main(String[] args) {
        String s = "tmmzuxt";
        Q3LengthOfLongestSubstring lengthOfLongestSubstring = new Q3LengthOfLongestSubstring();
        int res = lengthOfLongestSubstring.lengthOfLongestSubstring(s);
        System.out.println("res = " + res);
    }

    public int lengthOfLongestSubstring(String s) {
        int maxLen = 0;
        int left = 0, right = 0;
        int length = s.length();
        Set<Character> set = new HashSet<>();
        while (right < length) {
            char c = s.charAt(right);
            // 若碰到了重复字符
            if (set.contains(c)) {
                // 缩小窗口 直至不含该字符
                while (s.charAt(left) != c) {
                    set.remove(s.charAt(left));
                    left++;
                }
                left++;
            }
            // 时刻更新值
            maxLen = Math.max(maxLen, right - left + 1);
            // 更新字符状态
            set.add(c);
            // 向右扩展
            right++;
        }
        return maxLen;
    }

    public int lengthOfLongestSubstring1(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int left = 0;
        int maxLen = 0;
        int right = 0;
        int length = s.length();
        while (right < length) {
            char c = s.charAt(right);
            if (map.containsKey(c)) {
                left = Math.max(left, map.get(c) + 1);
            }
            maxLen = Math.max(maxLen, right - left + 1);
            map.put(c, right);
            right++;
        }
        return maxLen;
    }

}
